import java.util.ArrayList;


public class Main2 {
	
	public static void main(String[] args) {
		System.out.println("Example ((big woman man big house),cl)");
		String example = "((big woman man big house),cl)";
		String[] tokens = example.split(",");
		String sentence = tokens[0];
		String expectedValue = tokens[1];
		sentence = sentence.substring(2, sentence.length()-1);
		expectedValue = expectedValue.substring(0,expectedValue.length()-1);
		System.out.println("Sentence: "+sentence);
		System.out.println("Expected Value: "+expectedValue);
		
		System.out.println(bottomUp(sentence,expectedValue));
	}
	
	public static String bottomUp(String sentence, String expectedValue){
		int round = 0 ;
		ArrayList<String> rules = makeRules();
		boolean success = false;
		ArrayList<String> answers = new ArrayList<String>();
		ArrayList<String> newAnswers = new ArrayList<String>();
		ArrayList<String> alreadyConsideredStrings = new ArrayList<String>();
		answers.add(sentence);
		String phrase = "";
		
		
		while(!answers.isEmpty() && !answers.contains(expectedValue)){
			round = round + 1 ;
			System.out.println("\nRound "+round);
		
			for(String answer: answers) {
				for(int i = 0; i < answer.trim().split(" ").length; i++) {
					for(int j = i; j < answer.trim().split(" ").length; j++) {
						phrase = subList(answer, i, j);
						ArrayList<String> substitutions = getSub(phrase);
							for(int k = 0; k < substitutions.size(); k++) {
								String newanswer = applyRule(answer, i ,j ,substitutions.get(k));
							//	String newanswer = makeSub(answer,i , j, substitutions.get(k));
								if(!alreadyConsideredStrings.contains(newanswer)){
									newAnswers.add(newanswer);
									alreadyConsideredStrings.add(newanswer);
									System.out.println(newanswer);
								}
							}
					}
				}
			}

			for(String answer: newAnswers)
				answers.add(answer);
			newAnswers.clear();
		
		}
		
		if(answers.contains(expectedValue))
			success = true;
		
		if(success)
			return "Success";
		else
			return "Failure";
		
	}
	
	
	public static ArrayList<String> makeRules(){
		
		ArrayList<String> rules = new ArrayList<String>();
		rules.add("cl -> np vp np");
		rules.add("np -> adj n");
		rules.add("vp -> adv v");
		rules.add("vp -> v");
		rules.add("n -> man");
		rules.add("v -> man");
		rules.add("n -> woman");
		rules.add("adj -> big");
		rules.add("n -> house");
		return rules;
	}
	
	public static String[] rulesParser(String rule){//returns the left and right hand side separately and fixed them
		String[] tokens = rule.split("->");
		tokens[0] = tokens[0].substring(0, tokens[0].length()-1); //removes the space after the left hand side
		tokens[1] = tokens[1].substring(1); //removes the space before the right hand side
		return tokens;
	}
	
	public static String subList(String answer, int begin, int end) {
		String[] split = answer.split(" ");
		String ex = "";
		for(int i = begin; i <= end; i++) 
			if(i == end)
				ex += split[i];
			else
				ex += split[i] + " ";

			return ex;
	}
	
	public static ArrayList<String> getSub(String phrase) {
		ArrayList<String> substitutions = new ArrayList<String>();
		for(String rule: makeRules()){
			String[] parsedRule = rulesParser(rule);
			if(parsedRule[1].equals(phrase))
				substitutions.add(rule);
		}
		
		return substitutions;
	}
	
	public static String makeSub(String answer, int begin, int end, String thesub) {
		String phrase = subList(answer,begin,end);
		String[] parsedRule = rulesParser(thesub);
		phrase = parsedRule[0];
		

		return "";
	}
	
	
	public static String applyRule(String sentence,int i,int j,String rule){
		String subphrase = subList(sentence,i,j);
		String[]parsedRule = rulesParser(rule);
		subphrase = parsedRule[0]; // replaces the subphrase with the left hand side of the rule		
		
		String left = ""; 
		if(i-1>=0)
			left = subList(sentence,0,i-1);
		
		String right = "";
		if(j!=sentence.trim().split(" ").length -1)
			right = subList(sentence,j+1,sentence.trim().split(" ").length-1);
			
		String appliedRule = "";
		if(left != "") appliedRule += left + " ";
		appliedRule += subphrase;
		if(right != "") appliedRule += " " + right;
		return appliedRule;
		
	}

}
